package mao.algorithm.sort;

/**
 * @author Totoro
 * @date 2020/7/10
 * @explain:
 */

public class HeapSort {
    public static void main(String[] args) {
        int [] data = {23,45};
        //对堆进行初始化。
        for(int i=(data.length-1)/2;i>=0;i--){
            heapify(data,i,data.length);
        }
        heapSort(data);
        for(int i =0;i<data.length;i++){
            System.out.println(data[i]);
        }
    }
    public static void heapSort(int[] data){
        for (int i=data.length-1;i>=0;i--) {
            heapify(data,0,i+1);
            swap(data,0,i);
        }
    }
    public static void heapify(int[] data, int index, int lenght){
        int left = 2*index+1,right = 2*index+2;
        int maxIndex = index;
        //检查代码逐行检查。
        if (left < lenght && data[left]>data[maxIndex]){
            maxIndex = left;
        }
        if (right < lenght && data[right]>data[maxIndex]){
            maxIndex = right;
        }
        if (maxIndex != index) {
            swap(data, index, maxIndex);
            heapify(data, maxIndex, lenght);
        }
    }

    private static void swap(int[] data,int from,int to){
        int tmp = data[from];
        data[from] = data[to];
        data[to] = tmp;
    }
}
